﻿#include <iostream>

static int* getNextArr(const char* str)
{
    auto len = strlen(str);
    int* nextArr = (int*)malloc(len * sizeof(int));
    memset(nextArr, 0, len * sizeof(int));
    nextArr[0] = -1;

    int index = 2;
    int cn = 0;
    while (index < len)
    {
        if (str[index - 1] == str[cn])
        {
            nextArr[index++] = ++cn;
        }
        else if (nextArr[cn] >= 0)
        {
            cn = nextArr[cn];
        }
        else
        {
            nextArr[index++] = 0;
        }
    }

    return nextArr;
}

static int indexOf(const char* str, const char* subStr)
{
    auto strLen = strlen(str);
    auto subStrLen = strlen(subStr);
    if (subStrLen > strLen) return -1;

    if (subStrLen == strLen)
    {
        if (strcmp(str, subStr) == 0) return 0;

        return -1;
    }

    if (subStrLen == 1)
    {
        for (int i = 0; i < strLen; i++)
        {
            if (str[i] == subStr[0]) return i;
        }

        return -1;
    }

    auto nextArr = getNextArr(subStr);
    int index = 0;
    int subIndex = 0;
    while (index < strLen && subIndex < subStrLen)
    {
        if (str[index] == subStr[subIndex])
        {
            ++index;
            ++subIndex;
        }
        else if (nextArr[subIndex] >= 0)
        {
            subIndex = nextArr[subIndex];
        }
        else
        {
            ++index;
        }
    }

    free(nextArr);

    return subIndex == subStrLen ? index - subIndex : -1;
}

static bool isRotatingWord(const char* str1, const char* str2)
{
    auto len1 = strlen(str1);
    char* doubleStr = (char*)malloc(len1 * 2 + 1);
    memset(doubleStr, 0, len1 * 2 + 1);
    memcpy(doubleStr, str1, len1);
    memcpy(doubleStr + len1, str1, len1);
	
    bool res = indexOf(doubleStr, str2) != -1;
    free(doubleStr);
    return res;
}

/**
 * 如果一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫做str的旋转词。
 * 比如str="12345", str的旋转词有"12345"、"23451"、"34512"、"45123"和"51234"。
 * 给定两个字符串a和b，请判断a和b是否互为旋转词。
 * 比如:
 * a="cdab", b="abcd", 返回true
 * a="1ab2", b="ab12", 返回false
 * a="2ab1", b="ab12", 返回true
 *
 * 思路: 设c=a+a, 使用KMP算法，看b是否是c的子串.
 */
int main_RotatingWord()
{
    char str1[256] = "abcdef";
    char str2[256] = "efabcd";
    auto res = isRotatingWord(str1, str2);
    printf("%d\n", res);
    return 0;
}